package com.algorithms.techniques;

import java.util.Arrays;

public class CountingSort {

	private   int[] originalArray=null;
	private int[] countArray=null;
	private int[] sortedArray=null;
	public CountingSort(int[] inputArray,int k)
	{
		originalArray=inputArray;
		countArray = new int[k];
		sortedArray= new int[inputArray.length];
	}
	public void countSort()
	{
		printArray(originalArray,"originalArray");
		printArray(countArray,"countArray");
		for(int s :originalArray)
			countArray[s]=countArray[s]+1;
		printArray(countArray,"CountArray");
		for(int i=1;i<countArray.length ;i++)
			countArray[i]=countArray[i]+countArray[i-1];
		printArray(countArray,"CountArray");
		for(int i=sortedArray.length-1;i>=0;i++)
		{
			sortedArray[countArray[originalArray[i]]-1] =originalArray[i];
			countArray[originalArray[i]]=countArray[originalArray[i]]-1;
		}
	}
	
	public int[] getSortedArray()
	{
		printArray(sortedArray,"SortedArray");
		return sortedArray;
	}
	
	public void printArray(int[] array,String arrayName)
	{
		System.out.println("\nArrayLength=" + array.length + " ArrayName="+ arrayName);
		for(int a:array)
		{
			System.out.print(a + "\t");
		}
	}
}
